package interview.loop;

/**
 * Created with IntelliJ IDEA.
 * Description: 二分查找
 * User: xxm
 * Date: 2018-02-21
 * Time: 20:55
 */
public class BinarySearch {

    /**
     * Search element k in a sorted array.
     *
     * @param arr arr a sorted array
     * @param k   k the element to search
     * @return index in arr where k is. -1 if not found
     */
    public static int binarySearch(int[] arr, int k) {
        int a = 0;
        int b = arr.length;
        // Loop invariant: [a,b) is a valid range. (a <= b)
        // k may only be within range [a,b)
        while (a < b) {
            int m = a + (b - a) / 2; // (a+b)/2 may overflow!
            // b == a + 1: m = a
            // b == a + 2: m = a + 1
            if (k < arr[m]) {
                b = m;
            } else if (k > arr[m]) {
                a = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(
                BinarySearch.binarySearch(new int[]{1, 2, 10, 15, 100}, 15));
        System.out.println(
                BinarySearch.binarySearch(new int[]{1, 2, 10, 15, 100}, -2));
        System.out.println(
                BinarySearch.binarySearch(new int[]{1, 2, 10, 15, 100}, 101));
        System.out.println(
                BinarySearch.binarySearch(new int[]{1, 2, 10, 15, 100}, 13));
        System.out.println("========================");
        System.out.println(
                BinarySearch.binarySearch(new int[]{}, 15));
        System.out.println(
                BinarySearch.binarySearch(new int[]{15}, 15));
        System.out.println(
                BinarySearch.binarySearch(new int[]{12}, 15));
        System.out.println("========================");
        System.out.println(
                BinarySearch.binarySearch(new int[]{12, 13}, 13));
        System.out.println(
                BinarySearch.binarySearch(new int[]{12, 13}, 12));
    }
}
